#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int Vertex; /* 顶点编号类型 */

typedef struct EdgeNode *Position; /* 指针即结点位置 */
struct EdgeNode {
    Vertex dest; /* 边的另一端点编号 */
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *AdjList; /* 邻接表 */
struct HeadNode {
    Position adj; /* 邻接表头指针 */
};
typedef struct LGraphNode *LGraph; /* 邻接表表示的图 */
struct LGraphNode {
    int n_verts; /* 顶点数 */
    int m_edges; /* 边数 */
    AdjList *ver_list; /* 存储顶点邻接表 */
    bool directed; /* true为有向图，false为无向图 */
};
#define NIL -1 /* 顶点不存在时的返回值 */

void InitGraph(LGraph graph, int kMaxVertex, bool directed);
bool ExistEdge(LGraph graph, Vertex u, Vertex v);
void InsertEdge(LGraph graph, Vertex u, Vertex v);
LGraph BuildGraph();
LGraph ReverseGraph(LGraph graph);
int PostOrderDFS(LGraph graph, Vertex v, bool visited[], Vertex dfs_seq[],
                 int dfs_num);
void PrintV(LGraph graph, Vertex v, bool visited[]);
int StronglyConnectedComponents(LGraph graph);

int main(void) {
    LGraph graph;

    graph = BuildGraph();
    printf("%d\n", StronglyConnectedComponents(graph));

    return 0;
}

void InitGraph(LGraph graph, int kMaxVertex, bool directed) {
    /* 初始化一个空的图 */
    Vertex v;
    Position p;

    graph->n_verts = 0;
    graph->m_edges = 0;
    /* 声明邻接表头结点数组graph->ver_list[kMaxVertex] */
    graph->ver_list = (AdjList *)malloc(sizeof(AdjList) * kMaxVertex);
    for (v = 0; v < kMaxVertex; v++) {
        graph->ver_list[v] = (AdjList)malloc(sizeof(struct HeadNode));
        graph->ver_list[v]->adj = NULL;
    }
    graph->directed = directed;
}

bool ExistEdge(LGraph graph, Vertex u, Vertex v) {
    Position p;
    bool ret = false;

    if (u < graph->n_verts && v < graph->n_verts) {
        p = graph->ver_list[u]->adj;
        while (p != NULL && p->dest != v) {
            p = p->next;
        }
        if (p != NULL) {
            ret = true;
        }
    }
    return ret;
}

void InsertEdge(LGraph graph, Vertex u, Vertex v) {
    Position p;

    if (ExistEdge(graph, u, v) == false) {
        p = (Position)malloc(sizeof(struct EdgeNode));
        p->dest = v;
        p->next = graph->ver_list[u]->adj;
        graph->ver_list[u]->adj = p;
        graph->m_edges++;
    }
}

LGraph BuildGraph() {
    LGraph graph;
    int n, m, i;
    Vertex u, v;

    scanf("%d %d", &n, &m);
    graph = (LGraph)malloc(sizeof(struct LGraphNode));
    InitGraph(graph, n, true);
    graph->n_verts = n;
    for (i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        InsertEdge(graph, u, v);
    }
    return graph;
}

LGraph ReverseGraph(LGraph graph) {
    /* 创建graph的逆向图 */
    LGraph r_graph;
    Position p;
    Vertex u, v;

    r_graph = (LGraph)malloc(sizeof(struct LGraphNode));
    InitGraph(r_graph, graph->n_verts, true);
    r_graph->n_verts = graph->n_verts;
    for (u = 0; u < graph->n_verts; u++) {
        p = graph->ver_list[u]->adj;
        while (p != NULL) {
            v = p->dest; /* 对graph中的边<u,v> */
            InsertEdge(r_graph, v, u); /* 将<v,u>插入r_graph */
            p = p->next;
        }
    }
    return r_graph;
}

/* 算法7-18：后序DFS遍历记录顶点 PostOrderDFS(graph, v, visited, dfs_seq, dfs_num) */
int PostOrderDFS(LGraph graph, Vertex v, bool visited[], Vertex dfs_seq[],
                 int dfs_num) {
    Position p;

    visited[v] = true;
    p = graph->ver_list[v]->adj;
    while (p != NULL) {
        if (visited[p->dest] == false) {
            dfs_num = PostOrderDFS(graph, p->dest, visited, dfs_seq, dfs_num);
        }
        p = p->next;
    }
    dfs_seq[dfs_num] = v; /* v是第dfs_num个被访问的顶点 */
    return ++dfs_num;
}
/* 算法7-18 结束 */

/* 算法7-19：后序DFS遍历输出顶点 PrintV(graph, v, visited) */
void PrintV(LGraph graph, Vertex v, bool visited[]) {
    /* 后序遍历DFS输出顶点 */
    Position p;

    visited[v] = true;
    p = graph->ver_list[v]->adj;
    while (p != NULL) {
        if (visited[p->dest] == false) {
            PrintV(graph, p->dest, visited);
        }
        p = p->next;
    }
    printf(" %d", v);
}
/* 算法7-19 结束 */

/* 算法7-17：获取图的强连通分量 StronglyConnectedComponents (graph) */
int StronglyConnectedComponents(LGraph graph) {
    LGraph r_graph;
    Vertex v, *dfs_seq;
    bool *visited;
    int dfs_num, count;

    visited = (bool *)malloc(sizeof(bool) * graph->n_verts);
    for (v = 0; v < graph->n_verts; v++) {
        visited[v] = false; /* 初始化各顶点的已访问标志为未访问 */
    }
    dfs_seq = (Vertex *)malloc(sizeof(Vertex) * graph->n_verts);
    for (dfs_num = 0; dfs_num < graph->n_verts; dfs_num++) {
        dfs_seq[dfs_num] = NIL; /* 初始化各DFS访问序号对应的顶点为空 */
    }
    dfs_num = 0; /* 初始化后序深度优先遍历的序号 */
    for (v = 0; v < graph->n_verts; v++) {
        if (visited[v] == false) { /* 从一个未访问的顶点开始 */
            /* 后序DFS遍历graph，顺序记录访问的顶点 */
            dfs_num = PostOrderDFS(graph, v, visited, dfs_seq, dfs_num);
        }
    }
    r_graph = ReverseGraph(graph); /* 创建graph的逆向图 */
    for (v = 0; v < graph->n_verts; v++) {
        visited[v] = false; /* 初始化各顶点的已访问标志为未访问 */
    }
    count = 0; /* 初始化强连通分量计数器 */
    while (dfs_num > 0) {
        dfs_num--;
        /* 总是从dfs_num最大的未访问顶点出发 */
        v = dfs_seq[dfs_num];
        if (visited[v] == false) {
            printf("{"); /* 一个强连通分量的开始 */
            PrintV(r_graph, v, visited); /* 输出顶点 */
            printf(" }\n"); /* 一个强连通分量的结束 */
            count++; /* 统计强连通分量个数 */
        }
    }
    return count;
}
/* 算法7-17 结束 */